package math;

public class BigInt {

	/**
	 * a, b can be negative
	 */
	public String multiply(String a, String b) {
		int s = 1;
		int n = a.length();
		int m = b.length();
		StringBuilder sb = new StringBuilder();
		if (a.charAt(0) == '-' && b.charAt(0) != '-' || a.charAt(0) != '-'
				&& b.charAt(0) == '-') {
			s = -1;
		}
		int[] d = new int[m + n];
		for (int i = 0; i < n + m; ++i) {
			for (int j = 0; j <= Math.min(i, n - 1); ++j) {
				int p = n - 1 - j;
				int q = m - 1 - (i - j);
				if (q < 0 || q >= m || !Character.isDigit(b.charAt(q))
						|| !Character.isDigit(a.charAt(p))) {
					continue;
				}
				d[i] += (b.charAt(q) - '0') * (a.charAt(p) - '0');
			}
		}
		int carry = 0;
		int i = 0;
		for (; i < n + m; ++i) {
			d[i] += carry;
			carry = d[i] / 10;
			d[i] = d[i] % 10;
		}
		i = m + n - 1;
		while (i > 0 && d[i] == 0) {
			i--;
		}
		if ((i != 0 || d[0] != 0) && s == -1)
			sb.append('-');
		for (; i >= 0; --i)
			sb.append(d[i]);
		return sb.toString();
	}

	/**
	 * non-negative a, b
	 */
	public String add(String a, String b) {
		int n = a.length(), m = b.length();
		StringBuilder sb = new StringBuilder();
		int carry = 0;
		int i = 0;
		for (; i < Math.min(n, m); ++i) {
			int p = n - 1 - i, q = m - 1 - i;
			int v = (a.charAt(p) - '0') + (b.charAt(q) - '0');
			v += carry;
			carry = v / 10;
			v = v % 10;
			sb.append(v);
		}
		while (i < n) {
			int p = n - 1 - i++;
			int v = (a.charAt(p) - '0') + carry;
			carry = v / 10;
			v = v % 10;
			sb.append(v);
		}
		while (i < m) {
			int q = m - 1 - i++;
			int v = (b.charAt(q) - '0') + carry;
			carry = v / 10;
			v = v % 10;
			sb.append(v);
		}
		if (carry > 0)
			sb.append(carry);
		return sb.reverse().toString();
	}
}
